package com.LeeCode;

/**
 * 分割等和子集
 */

public class Code416 {
    public static void main(String[] args) {
        int[] nums = {1, 5, 11, 5};
        System.out.println(new Code416().canPartition(nums));
    }

    public boolean canPartition(int[] nums) {
        int len = nums.length;
        if (len < 2) { // 数量不够拆分
            return false;
        }
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 == 1) { // 和为奇数，不可能拆分
            return false;
        }
        int target = sum / 2;

        boolean[][] dp = new boolean[len][target + 1];
        for (int i = 0; i < len; i++) {  // 初始化第一列
            dp[i][0] = true;
        }
        if (nums[0] <= target) {
            dp[0][nums[0]] = true;  // 初始化第一行
        }
        for (int i = 1; i < len; i++) {
            for (int j = 1; j <= target; j++) {
                if (j < nums[i]) { // 无法选择该数
                    dp[i][j] = dp[i - 1][j];
                } else {  // 可以选择该数：选或不选
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                }
            }
        }
        return dp[len - 1][target];
    }
}
